class code3 {
    //不同路径 III
    //统计step(步数：0的个数+1) == count 
    int m,n;
    boolean[][] vis;
    int step = 1;
    int ret = 0;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        vis = new boolean[m][n];
        int bx = 0;
        int by = 0;
        //统计step 
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]==0) {
                    step++;
                } else if(grid[i][j]==1) {
                    bx = i;
                    by = j;
                }
            }
        }
        //得写在下面，不然step没有统计完
        vis[bx][by] = true;
        dfs(grid,bx,by,0);
        return ret;
    }
    void dfs(int[][] grid,int i,int j,int count) {
        //出口
        if(grid[i][j]==2) {
            if(count == step) {
                ret++;
            }
            return;
        }


        for(int k=0;k<4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y]!=-1) {
                vis[x][y] = true;
                dfs(grid,x,y,count+1);
                vis[x][y] = false;
            }
        }
    }
}